package com.leetcode;

import com.leetcode.entity.TreeNode;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
 * 前序遍历的过程：根节点、左子节点、右子节点
 * 中序遍历的过程：左子节点，根节点，右子节点
 *
 * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * Output: [3,9,20,null,null,15,7]
 *
 * 遇到树的问题，毫无疑问，肯定遍历
 *
 */
public class Offer07 {
    public static void main(String[] args) {
        int[] preorder = new int[]{3,9,20,15,7};
        int[] inorder = new int[]{9,3,15,20,7};
        TreeNode root = null;
        root = buildTree(root, preorder, inorder);

        // TODO 遍历root转换为数组
        System.out.println(root);
    }

    public static TreeNode buildTree(TreeNode node, int[] preorder, int[] inorder) {

        if (preorder.length < 1)
            return null;

        // TODO 查找根节点
        int root = preorder[0];
        node = new TreeNode(root);

        int rootIndex = getINOrderIndex(inorder, root);
        int prelen = preorder.length;
        // TODO 计算左边新的中序
        int[] leftPreorder = new int[rootIndex];
        int[] rightPreorder = new int[prelen - rootIndex - 1];
        int rightPreorderLen = prelen - rootIndex - 1;
        for (int i = 0; i < rootIndex; i++) {
            leftPreorder[i] = preorder[i+1];
        }
        for (int i = 0; i < rightPreorderLen; i++) {
            rightPreorder[i] = preorder[1 + rootIndex + i];
        }

        // TODO 计算新的中序
        int[] leftInorder = new int[rootIndex];
        int[] rightInorder = new int[rightPreorderLen];
        for (int i = 0; i < rootIndex; i++) {
            leftInorder[i] = inorder[i];
        }
        for (int i = 0; i < rightPreorderLen; i++) {
            rightInorder[i] = inorder[rootIndex + 1 + i];
        }

        node.setLeft(buildTree(node.getLeft(), leftPreorder, leftInorder));
        node.setRight(buildTree(node.getRight(), rightPreorder, rightInorder));

        return node;
    }

    /**
     * 查找中序数组的根节点所在索引位置
     * @param inorder
     * @param root
     * @return
     */
    public static int getINOrderIndex(int[] inorder, int root) {
        int len = inorder.length;
        for (int i = 0; i < len; i++) {
            if (inorder[i] == root)
                return i;
        }
        return -1;
    }
}
